package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Lc399UnionFindSet {


    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

        int size = equations.size() ;
        HashMap<String, Integer> map = new HashMap<>(); //把equations中的字符串映射成0 ~ x的数字

        int idx = 0;
        UnionFindSet unionFindSet = new UnionFindSet(size * 2);
        for (int i = 0; i < equations.size(); i++) {
            String a = equations.get(i).get(0);
            String b = equations.get(i).get(1);
            if (!map.containsKey(a)) {
                map.put(a, idx);
                idx ++;
            }
            if (!map.containsKey(b)) {
                map.put(b, idx);
                idx++;
            }
            unionFindSet.union(map.get(a), map.get(b), values[i]);
        }
        double[] ans = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            if (!map.containsKey(queries.get(i).get(0)) ||
                    !map.containsKey(queries.get(i).get(1))) {
                ans[i] = -1.0;
                continue;
            }
            ans[i] = unionFindSet.getAns(map.get(queries.get(i).get(0)), map.get(queries.get(i).get(1)));
        }
        return ans;
    }

//[["a","b"],["e","f"],["b","e"]]
//        [3.4,1.4,2.3]
//        [["b","a"],["a","f"],["f","f"],["e","e"],["c","c"],["a","c"],["f","e"]]
//
//    public static void main(String[] args) {
//        List<List<String>> l = new ArrayList<>();
//        List<String> l1 = new ArrayList<>();
//        l1.add("a");
//        l1.add("b");
//        List<String> l2 = new ArrayList<>();
//        l2.add("e");
//        l2.add("f");
//        List<String> l3 = new ArrayList<>();
//        l3.add("b");
//        l3.add("e");
//        l.add(l1);
//        l.add(l2);
//        l.add(l3);
//        double[] val = new double[]{3.4, 1.4, 2.3};
//        List<List<String>> q = new ArrayList<>();
//        List<String> q1 = new ArrayList<>();
//        q1.add("b");
//        q1.add("a");
//        List<String> q2 = new ArrayList<>();
//        q2.add("a");
//        q2.add("f");
//        q.add(q1);
//        q.add(q2);
//
//        Lc399UnionFindSet lc399UnionFindSet = new Lc399UnionFindSet();
//        double[] ans = lc399UnionFindSet.calcEquation(l,val,q);
//        for (int i = 0; i < ans.length; i++) {
//            System.out.println(ans[i]);
//        }
//    }


}

class UnionFindSet {

    private int[] parent ; //parent[i]:保存节点i的父节点
    private double[] weight; // weight[i]:保存节点i到父节点的权值，即i / parent[i]
    public UnionFindSet(int size){
        this.parent = new int[size];
        this.weight = new double[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i; // 初始化每个节点都指向自己
            weight[i] = 1d;
        }
    }

    public int find(int x) {
        if (x != parent[x]) {
            int origin = parent[x];
            parent[x] = find(parent[x]);
            weight[x] *= weight[origin];
        }
        return parent[x];
    }

    public void union(int x, int y, double w) {
        int xParent = find(x);
        int yParent = find(y);
        if (xParent != yParent) { //进行合并
            parent[xParent] = yParent;
            weight[xParent] = w * weight[y] / weight[x];
        }
    }

    public double getAns(int x, int y) {
        int xParent = find(x);
        int yParent = find(y);
        if (xParent != yParent)
            return -1.0;
        return weight[x] / weight[y];
    }
}